//
//  GPAlgorithm.swift
//  SwiftDemo
//
//  Created by xinchen on 2024/7/8.
//

import Foundation


class GPAlgorithm: NSObject {
    
    static public let shared = GPAlgorithm()
    
    /**
     有序数组合并
     */
    func mergeList(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var results = nums1 + nums2
        var index1 = nums1.count - 1
        var index2 = nums2.count - 1
        
        while index2 >= 0 {
            if index1 >= 0, nums1[index1] > nums2[index2] {
                results[index1 + index2 + 1] = nums1[index1]
                index1 -= 1
            } else {
                results[index1 + index2 + 1] = nums2[index2]
                index2 -= 1
            }
        }
        
        return results
    }
    
    /**
     合并两个有序数组
     给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

     请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列
     */
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        // 方案一
//        if m == 0 {
//            nums1 = nums2
//            return
//        }
//        if n == 0 {
//            return
//        }
//        var mtenp = m
//        var mIndex = 0
//        var nIndex = 0
//        var count = nums1.count
//        
//        for index in 0..<count {
//            if mIndex < count {
//                if nIndex < n {
//                    if nums1[mIndex] > nums2[nIndex] {
//                        nums1.insert(nums2[nIndex], at: mIndex)
//                        nums1.removeLast()
//                        mIndex += 1
//                        nIndex += 1
//                        mtenp += 1
//                    } else {
//                        if mtenp == mIndex {
//                            nums1.insert(nums2[nIndex], at: mIndex)
//                            nums1.removeLast()
//                            nIndex += 1
//                            mtenp += 1
//                        }
//                        mIndex += 1
//                    }
//                } else {
//                    return
//                }
//            } else {
//                break
//            }
//        }
        
        // 方案二
//        nums1.removeSubrange(m..<nums1.count)
//        nums1.append(contentsOf: nums2)
//        nums1.sort()
        
        // 方案三 双指针 倒叙的方式进行， mIndex + nIndex + 1 即代表当前的位置
        var mIndex = m - 1
        var nIndex = n - 1
        
        while nIndex >= 0 {
            if mIndex >= 0, nums1[mIndex] > nums2[nIndex] {
                nums1[mIndex + nIndex + 1] = nums1[mIndex]
                mIndex -= 1
            } else {
                nums1[mIndex + nIndex + 1] = nums2[nIndex]
                nIndex -= 1
            }
        }
        
    }
    
    /**
     n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

     你需要按照以下要求，给这些孩子分发糖果：

     每个孩子至少分配到 1 个糖果。
     相邻两个孩子评分更高的孩子会获得更多的糖果。
     请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
     */
    func candy(_ ratings: [Int]) -> Int {
        let length = ratings.count
        if length == 1 {
            return 1
        }
        var leftArray = Array.SubSequence(repeating: 1, count: length)
        for index in 1..<length {
            if ratings[index] > ratings[index-1] {
                leftArray[index] = leftArray[index-1] + 1
            }
        }
        
        var rightArray = Array.SubSequence(repeating: 1, count: length)
        for index in 0..<length-1 {
            if ratings[length-2-index] > ratings[length-1-index] {
                rightArray[length-2-index] = rightArray[length-1-index] + 1
            }
        }
        
        var count = 0
        for index in 0..<length {
            count = count + max(leftArray[index], rightArray[index])
        }
        
        return count
    }
    
    /**   392. 判断子序列
     给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

     字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

     进阶：

     如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
     */
    func isSubsequence(_ s: String, _ t: String) -> Bool {
        
        let sArray = Array(s)
        let tArray = Array(t)
        
        if sArray.count == 0 {
            return true
        }
        
        var sIndex = 0
        for i in 0..<tArray.count {
            if sIndex < sArray.count {
                if tArray[i] == sArray[sIndex] {
                    if sIndex == sArray.count - 1 {
                        return true
                    }
                    sIndex += 1
                }
            }
        }
        
        return false
    }
    
    /**  167. 两数之和 II - 输入有序数组
     给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

     以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

     你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素
     */
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        /**
        方法一   swift的特性
        var list = numbers
        for index in 0..<numbers.count {
            list.removeFirst()
            let poorVlue = target - numbers[index]
            if let indx = list.firstIndex(of: poorVlue), indx != index {
                return [index, indx]
            }
        }
        return[1, 2]   7 1,     6  2,   5  3,   2  4
         */
        /**
        // 方法二  hash
        var dict = [Int: Int]()
        for index in 0..<numbers.count {
            if dict[target - numbers[index]] != nil {
                return [dict[target - numbers[index]]!, index + 1]
            }
            dict[numbers[index]] = index + 1
        }
        return []
         */
        
        // 方法三 双指针  推荐
        var left = 0
        var right = numbers.count - 1
        while left < right {
            let and = numbers[left]+numbers[right]
            if and < target {
                left += 1
            } else if and > target {
                right -= 1
            } else {
                return[left + 1, right + 1]
            }
        }
        return []
    }
    
    /** 11. 盛最多水的容器
     给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

     找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

     返回容器可以储存的最大水量。  54837
     
     题解：
     当前盛水 = min(height[left], height[right]) * (right - left)，高度越高，盛水越多
     使用双指针的方法进行，当左指针的值 大于 右指针的值，右指针前移 -1，反之 左指针后移 +1，获取最大值
     */
    func maxArea(_ height: [Int]) -> Int {
        var left = 0
        var right = height.count - 1
        var count = 0
        while left < right {
            count = max(min(height[left], height[right]) * (right - left), count)
            if height[left] >= height[right] {
                right -= 1
            } else {
                left += 1
            }
        }
        return 0
    }
    
    /** 15. 三数之和
     给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

     你返回所有和为 0 且不重复的三元组。

     注意：答案中不可以包含重复的三元组。
     
     题解：双指针的方式，
     1、将数组排序（sorted），使用 for 循环，确定一个值
     2、在使用双指针的形式确定后面两个值，判断三者的和
            大于0，右边的指针前移 -1
            小于0，左边的指针后移 +1
            等于0，判断数组中是否有该值，有的话视为重复，然后右边的指针前移 -1，左边的指针后移 +1
     */
    func threeSum(_ nums: [Int]) -> [[Int]] {
        if nums.count < 3 {
            return []
        }
        let array = nums.sorted()
        var list = [[Int]]()
        for index in 0..<array.count {
            var left = index + 1
            var right = array.count - 1
            while left < right {
                if array[index] + array[left] + array[right] == 0 {
                    let arr = [array[index], array[left], array[right]]
                    if !list.contains(arr) {
                        list.append(arr)
                    }
                    left += 1
                    right -= 1
                } else if array[index] + array[left] + array[right] < 0 {
                    left += 1
                } else if array[index] + array[left] + array[right] > 0 {
                    right -= 1
                }
            }
        }
        return list
    }
    
    /**  209. 长度最小的子数组
     给定一个含有 n 个正整数的数组和一个正整数 target 。
     
     找出该数组中满足其总和大于等于 target 的长度最小的
     子数组
      [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     
     题解：
        使用滑动窗口的思想
        list 就是这个窗口的内容，当窗口的数据和 total 大于 target时，判断 total - list.first 与target的大小，
            当大于target时，窗口list移除最前面的数据，total也对应减去该值，循环结束记录窗口的长度，
            以此往后推，每次用 minLength来记录获取到的最小窗口内容长度
     */
    func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
        
        var total = 0
        var list = [Int]()
        var minLength = nums.count
        for index in 0..<nums.count {
            total += nums[index]
            list.append(nums[index])
            if total >= target {
                while total - list.first! >= target {
                    total -= list.first!
                    list.removeFirst()
                }
                minLength = min(minLength, list.count)
            }
            if index == nums.count - 1, total < target {
                return 0
            }
        }
        return minLength
        // 精简
//        var result = Int.max // 窗口的内容长度
//        var sum = 0  // 窗口数据的和
//        var starIndex = 0  // 窗口中的第一个数据在 nums的位置
//        for endIndex in 0..<nums.count {
//            sum += nums[endIndex]
//            while sum >= target {
//                result = min(result, endIndex - starIndex + 1) // result 记录最小的窗口内容长度
//                sum -= nums[starIndex] // 去除窗口中的第一个数据
//                starIndex += 1
//            }
//        }
//
//        return result == Int.max ? 0 : result
    }

    /** 3. 无重复字符的最长子串
     给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
     
     题解：
     跟上面的问题一样，使用滑动窗口的逻辑进行
     窗口是 result、当字符在窗口时需要截取掉该字符之前的字符（包含该字符）
     */
    func lengthOfLongestSubstring(_ s: String) -> Int {
        let array = Array(s)
        var maxLength = 0
        var result = ""
        for index in 0..<array.count {
            if result.contains(array[index]) {
                if let range = result.range(of: String(array[index])) {
                    result = String(result[range.upperBound...])
                }
            }
            result = result + "\(array[index])"
            maxLength = max(maxLength, result.count)
        }
        return maxLength
    }
    
    /** 30. 串联所有单词的子串
     给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

      s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

     例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
     返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
     
     示例 2：

     输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
     输出：[]
     解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
     s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
     所以我们返回一个空数组。

     
     示例 3：

     输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
     输出：[6,9,12]
     解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
     子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
     子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
     子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
     
     题解：暴力求解，其它方式暂时没想到
     
     */
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        
        if words.count == 0 || (words.count * words.first!.count) > s.count {
            return []
        }
        let length = words.first!.count
        let windowLength = length * words.count
        var finalString = s
        var list = [Int]()
        var tempIndex = 0
        while finalString.count >= windowLength {
            let startIndex = finalString.index(finalString.startIndex, offsetBy: 0)
            let endIndex = finalString.index(finalString.startIndex, offsetBy: windowLength)
            var substring = String(finalString[startIndex...endIndex])
            var hhhh = false
            for index in 0..<words.count {
                if substring.contains(words[index]) {
                    substring = substring.replacingOccurrences(of: words[index], with: "")
                } else {
                    tempIndex += 1
                    hhhh = true
                    finalString = String(finalString.dropFirst())
                    break
                }
            }
            if !hhhh {
                list.append(tempIndex)
            }
        }
        
        return []
    }
    
    /** 76. 最小覆盖子串
     给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     注意：
     对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     如果 s 中存在这样的子串，我们保证它是唯一的答案。
     
     题解：暂时没有
     */
    func minWindow(_ s: String, _ t: String) -> String {
        let length = t.count
        let array = Array(s)
        var list = Array(t)
        var result = ""
        var tempStr = ""
        for index in 0..<array.count {
            let chart = array[index]
            if list.contains(chart) {
                if let index = list.firstIndex(of: chart) {
                    list.remove(at: index)
                    tempStr = tempStr + "\(chart)"
                }
                if list.count == 0 {
                    list = Array(t)
                    if result.count == 0 {
                        result = tempStr
                    } else {
                        if tempStr.count < result.count {
                            result = tempStr
                        }
                    }
                    tempStr = ""
                }
            } else {
                if tempStr.count > 0 {
                    tempStr = tempStr + "\(chart)"
                }
            }
        }
        
        return result
    }
    
    
    
    
    
    
    
    
    
    
    
}



